The present invention relater-to met hods and apparatus for calculating scalar products over Galois Field (GF2) in general, and for calculating a parity check of a binary vector, in particular, These scalar operations are employable in communication systems which employ coding techniques (e.g. block codes or convolutional coder) and synchronizaton mechanisms.
A scalar product of two binary vectors over GF2 plays a crucial part in a variety of applications. such as error correcting codes, codes for synchronization, parity check, binary convolution and multiplication of polynomials over GF2.
A scalar product is defined as follows;
Let A=(a1, a2, . . . an) and Bxe2x88x92(b1, b2, . . . bn), where both A and B are binary vectors of length n.
Therefore, the resultant scalar product is: Z=(A,B)2  Z  =                    (                  A          ,          B                )            2        =                  (                              ∑                          i              =              1                        n                    ⁢                      xe2x80x83                    ⁢                                    a              1                        ⁢                          b              1                                      )            ⁢              xe2x80x83            ⁢      mod2      
mod2
where Z is the parity check of selected columns of binary vector A, and where binary vector B is used as a mask defining the selected columns. Where the binary code of B is defined as 0, the associated binary code of A is masked, and a parity check is not calculated. Where the binary code of B is defined as 1, a parity check of the associated binary code of A is calculated. As such, when B is defined as an all-ones vector, parity of the entire vector A is computed.
It is an object of the present invention to provide a mechanism that computes a scalar product (SP) of two binary vectors of length n less than =SIZE within one cycle, where n is the length of a first binary vector and SIZE is the length of a second binary vector. Typically, the second binary vector is a word of either 16, 20, 24, 32, 40. 48 or 56 bits, or any other length less than 56 bits.
Furthermore, if n greater than SIZE less than 2*SIZE then it is possible to perform the scalar product within 2 cycles by activating a special include zero switch. It is additionally noted that if n greater than 2*SIZE, the scalar product is performed within             [              n        SIZE            ]        xc3x97          3      /      2        ⁢          xe2x80x83        ⁢    cycles    ,
where   [      n    SIZE    ]
is a minimal integer equal to or greater than       n    SIZE    .
Furthermore, in several applications, such as convolutional codes or cyclic linear block codes, the information is represented as a polynomial of degree n greater than  greater than SIZE.
The encoder generates the encoded data by multiplying it with generating polynomials of degree less or equal to SIZE. The present invention supports this computation with complexity of n cycles per generating polynomial,
A typical CPU supports bit by bit multiple input XOR operation, therefore, it takes n cycles to check the parity of a vector of length n. To overcome this drawback, in several applications external hardware is added. Another approach, for example in convolutional codes, is to implement the encoder as state machine.
There is therefore provided in a preferred embodiment of the present invention, a multiple input XOR for determining the parity of a vector.
There is additionally provided an apparatus for determining the parity of a vector, The apparatus includes a storage unit for storing an input vector of length N and a multiple input XOR for determining the parity of M bits of the input vector and for generating a parity bit. Alternatively, the apparatus further includes means for providing the bits of the input vector and the parity bit to the XOR, such that the parity of the entire input vector is determined.
Preferably the apparatus also includes means for generating an activation means, or switch, which considers the value of the parity bit, and dependent therefrom, activates conditional instructions. The apparatus may also includes an accumulator for storing a second vector and an input carry means. The input carry means, upon receipt of the parity bit, inputs the most significant bit from the accumulator into the least significant bit of the storage unit.
Preferably the apparatus further includes shift means for shifting the input vector one bit, within the storage unit, upon receipt of the most significant bit. In addition, preferably all of the means operate independently.